home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-13 / folded_u.zip / EXAMPLE.C < prev    next >
C/C++ Source or Header  |  1991-03-04  |  11KB  |  270 lines
  1. /*@/// Intro */
  2. /**************************************************************
  3.         LZSS.C -- A Data Compression Program
  4.         (tab = 4 spaces)
  5. ***************************************************************
  6.         4/6/1989 Haruhiko Okumura
  7.         Use, distribute, and modify this program freely.
  8.         Please send me your improved versions.
  9.                 PC-VAN          SCIENCE
  10.                 NIFTY-Serve     PAF01022
  11.                 CompuServe      74050,1022
  12. **************************************************************/
  13. /*@\\\*/
  14. /*@/// includes */
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <ctype.h>
  19. /*@\\\*/
  20. /*@/// defines */
  21. #define N                4096   /* size of ring buffer */
  22. #define F                  18   /* upper limit for match_length */
  23. #define THRESHOLD       2   /* encode string into position and length
  24.                                                    if match_length is greater than this */
  25. #define NIL                     N       /* index for root of binary search trees */
  26. /*@\\\*/
  27. /*@/// global variables */
  28. unsigned long int
  29.                 textsize = 0,   /* text size counter */
  30.                 codesize = 0,   /* code size counter */
  31.                 printcount = 0; /* counter for reporting progress every 1K bytes */
  32. unsigned char
  33.                 text_buf[N + F - 1];    /* ring buffer of size N,
  34.                         with extra F-1 bytes to facilitate string comparison */
  35. int             match_position, match_length,  /* of longest match.  These are
  36.                         set by the InsertNode() procedure. */
  37.                 lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
  38.                         parents -- These constitute binary search trees. */
  39. FILE    *infile, *outfile;  /* input & output files */
  40. /*@\\\*/
  41.  
  42. /*@/// void InitTree(void) */
  43. void InitTree(void)  /* initialize trees */
  44. {
  45.         int  i;
  46.  
  47.         /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  48.            left children of node i.  These nodes need not be initialized.
  49.            Also, dad[i] is the parent of node i.  These are initialized to
  50.            NIL (= N), which stands for 'not used.'
  51.            For i = 0 to 255, rson[N + i + 1] is the root of the tree
  52.            for strings that begin with character i.  These are initialized
  53.            to NIL.  Note there are 256 trees. */
  54.  
  55.         for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  56.         for (i = 0; i < N; i++) dad[i] = NIL;
  57. }
  58. /*@\\\*/
  59. /*@/// void InsertNode(int r) */
  60. void InsertNode(int r)
  61. /*@/// description */
  62. /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  63.    trees (text_buf[r]'th tree) and returns the longest-match position
  64.    and length via the global variables match_position and match_length.
  65.    If match_length = F, then removes the old node in favor of the new
  66.    one, because the old one will be deleted sooner.
  67.    Note r plays double role, as tree node and position in buffer. */
  68. /*@\\\*/
  69. {
  70.         int  i, p, cmp;
  71.         unsigned char  *key;
  72.  
  73.         cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  74.         rson[r] = lson[r] = NIL;  match_length = 0;
  75.         for ( ; ; ) {
  76.                 if (cmp >= 0) {
  77.                         if (rson[p] != NIL) p = rson[p];
  78.                         else {  rson[p] = r;  dad[r] = p;  return;  }
  79.                 } else {
  80.                         if (lson[p] != NIL) p = lson[p];
  81.                         else {  lson[p] = r;  dad[r] = p;  return;  }
  82.                 }
  83.                 for (i = 1; i < F; i++)
  84.                         if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  85.                 if (i > match_length) {
  86.                         match_position = p;
  87.                         if ((match_length = i) >= F)  break;
  88.                 }
  89.         }
  90.         dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  91.         dad[lson[p]] = r;  dad[rson[p]] = r;
  92.         if (rson[dad[p]] == p) rson[dad[p]] = r;
  93.         else                   lson[dad[p]] = r;
  94.         dad[p] = NIL;  /* remove p */
  95. }
  96. /*@\\\*/
  97. /*@/// void DeleteNode(int p) */
  98. void DeleteNode(int p)
  99. {
  100.         int  q;
  101.  
  102.         if (dad[p] == NIL) return;  /* not in tree */
  103.         if (rson[p] == NIL) q = lson[p];
  104.         else if (lson[p] == NIL) q = rson[p];
  105.         else {
  106.                 q = lson[p];
  107.                 if (rson[q] != NIL) {
  108.                         do {  q = rson[q];  } while (rson[q] != NIL);
  109.                         rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  110.                         lson[q] = lson[p];  dad[lson[p]] = q;
  111.                 }
  112.                 rson[q] = rson[p];  dad[rson[p]] = q;
  113.         }
  114.         dad[q] = dad[p];
  115.         if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
  116.         dad[p] = NIL;
  117. }
  118. /*@\\\*/
  119. /*@/// void Encode(void) */
  120. void Encode(void)
  121. {
  122.         int  i, c, len, r, s, last_match_length, code_buf_ptr;
  123.         unsigned char  code_buf[17], mask;
  124.  
  125. /*@///         start-up */
  126. InitTree();  /* initialize trees */
  127. code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and
  128.         code_buf[0] works as eight flags, "1" representing that the unit
  129.         is an unencoded letter (1 byte), "0" a position-and-length pair
  130.         (2 bytes).  Thus, eight units require at most 16 bytes of code. */
  131. code_buf_ptr = mask = 1;
  132. s = 0;  r = N - F;
  133. for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with
  134.         any character that will appear often. */
  135. for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  136.         text_buf[r + len] = c;  /* Read F bytes into the last F bytes of
  137.                 the buffer */
  138. if ((textsize = len) == 0) return;  /* text of size zero */
  139. for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings,
  140.         each of which begins with one or more 'space' characters.  Note
  141.         the order in which these strings are inserted.  This way,
  142.         degenerate trees will be less likely to occur. */
  143. InsertNode(r);  /* Finally, insert the whole string just read.  The
  144.         global variables match_length and match_position are set. */
  145. /*@\\\*/
  146. /*@///         main loop */
  147. do {
  148.         if (match_length > len) match_length = len;  /* match_length
  149.                 may be spuriously long near the end of text. */
  150.         if (match_length <= THRESHOLD)
  151. /*@///           don't code: send one byte */
  152. {
  153.         match_length = 1;  /* Not long enough match.  Send one byte. */
  154.         code_buf[0] |= mask;  /* 'send one byte' flag */
  155.         code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
  156. }
  157. /*@\\\*/
  158.         else
  159. /*@///           code: send position and length pair */
  160. {
  161.         code_buf[code_buf_ptr++] = (unsigned char) match_position;
  162.         code_buf[code_buf_ptr++] = (unsigned char)
  163.                 (((match_position >> 4) & 0xf0)
  164.           | (match_length - (THRESHOLD + 1)));  /* Send position and
  165.                         length pair. Note match_length > THRESHOLD. */
  166. }
  167. /*@\\\*/
  168.         if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
  169.                 for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
  170.                         putc(code_buf[i], outfile);     /* code together */
  171.                 codesize += code_buf_ptr;
  172.                 code_buf[0] = 0;  code_buf_ptr = mask = 1;
  173.         }
  174.         last_match_length = match_length;
  175. /*@///         manage buffer */
  176. for (i = 0; i < last_match_length &&
  177.                 (c = getc(infile)) != EOF; i++) {
  178.         DeleteNode(s);          /* Delete old strings and */
  179.         text_buf[s] = c;        /* read new bytes */
  180.         if (s < F - 1) text_buf[s + N] = c;  /* If the position is
  181.                 near the end of buffer, extend the buffer to make
  182.                 string comparison easier. */
  183.         s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
  184.                 /* Since this is a ring buffer, increment the position
  185.                    modulo N. */
  186.         InsertNode(r);  /* Register the string in text_buf[r..r+F-1] */
  187. }
  188. /*@\\\*/
  189. /*@///         report progress */
  190. if ((textsize += i) > printcount) {
  191.         printf("%12ld\r", textsize);  printcount += 1024;
  192.                 /* Reports progress each time the textsize exceeds
  193.                    multiples of 1024. */
  194. }
  195. /*@\\\*/
  196. /*@///         After the end of text... */
  197. while (i++ < last_match_length) {
  198.         DeleteNode(s);                                  /* no need to read, but */
  199.         s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
  200.         if (--len) InsertNode(r);               /* buffer may not be empty. */
  201. }
  202. /*@\\\*/
  203. } while (len > 0);      /* until length of string to be processed is zero */
  204. /*@\\\*/
  205.         if (code_buf_ptr > 1) {         /* Send remaining code. */
  206.                 for (i = 0; i < code_buf_ptr; i++) putc(code_buf[i], outfile);
  207.                 codesize += code_buf_ptr;
  208.         }
  209.         printf("In : %ld bytes\n", textsize);   /* Encoding is done. */
  210.         printf("Out: %ld bytes\n", codesize);
  211.         printf("Out/In: %.3f\n", (double)codesize / textsize);
  212. }
  213. /*@\\\*/
  214. /*@/// void Decode(void) */
  215. void Decode(void)       /* Just the reverse of Encode(). */
  216. {
  217.         int  i, j, k, r, c;
  218.         unsigned int  flags;
  219.  
  220.         for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  221.         r = N - F;  flags = 0;
  222.         for ( ; ; ) {
  223.                 if (((flags >>= 1) & 256) == 0) {
  224.                         if ((c = getc(infile)) == EOF) break;
  225.                         flags = c | 0xff00;      /* uses higher byte cleverly */
  226.                 }                                /* to count eight */
  227.                 if (flags & 1)
  228. /*@///                   copy one byte */
  229. {
  230.         if ((c = getc(infile)) == EOF) break;
  231.         putc(c, outfile);  text_buf[r++] = c;  r &= (N - 1);
  232. }
  233. /*@\\\*/
  234.                 else
  235. /*@///                   decode */
  236. {
  237.         if ((i = getc(infile)) == EOF) break;
  238.         if ((j = getc(infile)) == EOF) break;
  239.         i |= ((j & 0xf0) << 4);  j = (j & 0x0f) + THRESHOLD;
  240.         for (k = 0; k <= j; k++) {
  241.                 c = text_buf[(i + k) & (N - 1)];
  242.                 putc(c, outfile);  text_buf[r++] = c;  r &= (N - 1);
  243.         }
  244. }
  245. /*@\\\*/
  246.         }
  247. }
  248. /*@\\\*/
  249.  
  250. /*@/// int main(int argc, char *argv[]) */
  251. int main(int argc, char *argv[])
  252. {
  253.         char  *s;
  254.  
  255.         if (argc != 4) {
  256.                 printf("'lzss e file1 file2' encodes file1 into file2.\n"
  257.                            "'lzss d file2 file1' decodes file2 into file1.\n");
  258.                 return EXIT_FAILURE;
  259.         }
  260.         if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  261.          || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  262.          || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  263.                 printf("??? %s\n", s);  return EXIT_FAILURE;
  264.         }
  265.         if (toupper(*argv[1]) == 'E') Encode();  else Decode();
  266.         fclose(infile);  fclose(outfile);
  267.         return EXIT_SUCCESS;
  268. }
  269. /*@\\\*/
  270.